package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.LinkedList;
import java.util.List;

/**
 * @author feizns
 * @since 2020/3/20
 */
public class PathSum2 {

    public static void main(String[] args) {
    }

    static List<List<Integer>> ans = new LinkedList<>();
    static LinkedList<Integer> curt = new LinkedList<>();

    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        dfs(root, 0, sum);
        return ans;
    }

    private static void dfs(TreeNode root, int val, int sum) {
        if ( root != null ) {
            curt.add(root.val);
            val += root.val;
            if ( val == sum && root.left == null && root.right == null ) {
                ans.add(curt);
                curt = new LinkedList<>(curt);
            }
            dfs(root.left, val, sum);
            dfs(root.right, val, sum);
            curt.removeLast();
        }
    }

}
